package gold.gold04;

/**
 *
 */
public class S1009排序矩阵查找 {
    /**
     * 100, 写过几次, 从右上角查找。这个不算二分查找吧。
     * 注意这里如果target不存在, 其实是不用考虑的, 不存在也会搜索到边界值。
     * 不存在的话也是会比一个边界值小或者比一个边界值大, 都是在最后得到的, 在中途无法判断。
     * 把return true的判断移到了最后, 从88->100, 总之做判断的时候我们应该把最不经常发生的情况移到最后。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rowPosi = 0, colPosi = matrix[0].length - 1;
        //boolean res = false;
        while(rowPosi < matrix.length && colPosi >= 0){
            if(matrix[rowPosi][colPosi] > target) colPosi--;
            else if(matrix[rowPosi][colPosi] < target) rowPosi++;
            else return true;
        }
        return false;
    }
}
